package cn.springcloud.fix.demo.leecode;

import java.util.Stack;

public class Test01 {

    public static void main(String[] args) {
        int r = scoreOfParentheses("(()(()))");
        System.out.println(r);
    }

//    private static int scoreOfParentheses(String s) {
//        return F(s, 0, s.length());
//    }

//    private static int F(String S, int i, int j) {
//        int ans = 0, bal = 0;
//        for (int k = i; k < j; ++k) {
//            bal += S.charAt(k) == '(' ? 1 : -1;
//            if (bal == 0) {
//                if (k - i == 1) {
//                    ans++;
//                } else {
//                    ans += 2 * F(S, i + 1, k);
//                }
//                i = k + 1;
//            }
//        }
//        return ans;
//    }

    private static int scoreOfParentheses(String string) {
        int a = -1, bal = 0, score = 0;
        for (int i = 0; i < string.length(); i++) {
            if (a < 0) a = i;

            bal += string.charAt(i) == '(' ? 1 : -1;
            if (bal == 0) {
                if (i - a == 1) {
                    score++;
                } else {
                    String s = string.substring(a + 1, i);
                    score += 2 * scoreOfParentheses(s);
                }
                a = -1;
            }
        }
        return score;
    }

    private static int scoreOfParentheses2(String S) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // The score of the current frame

        for (char c : S.toCharArray()) {
            if (c == '(')
                stack.push(0);
            else {
                int v = stack.pop();
                int w = stack.pop();
                stack.push(w + Math.max(2 * v, 1));
            }
        }
        return stack.pop();
    }
}
